package com.shm.leetcode;

import java.util.ArrayList;

/**
 * 886. 可能的二分法
 * 给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
 *
 * 每个人都可能不喜欢其他人，那么他们不应该属于同一组。
 *
 * 形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
 *
 * 当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
 *
 *
 *
 * 示例 1：
 *
 * 输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
 * 输出：true
 * 解释：group1 [1,4], group2 [2,3]
 * 示例 2：
 *
 * 输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
 * 输出：false
 * 示例 3：
 *
 * 输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= N <= 2000
 * 0 <= dislikes.length <= 10000
 * dislikes[i].length == 2
 * 1 <= dislikes[i][j] <= N
 * dislikes[i][0] < dislikes[i][1]
 * 对于 dislikes[i] == dislikes[j] 不存在 i != j
 * @author SHM
 */
public class PossibleBipartition {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        ArrayList<Integer>[] graph = new ArrayList[N+1];
        int n = N;
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<Integer>();
        }

        for(int[] dis:dislikes){
            graph[dis[0]].add(dis[1]);
            graph[dis[1]].add(dis[0]);
        }
        UnionFind uf = new UnionFind(n);
        for(int i=1;i<=n;i++){
            ArrayList<Integer> ver = graph[i];
            for(int v:ver){
                if(uf.connect(v,i)){
                    return false;
                }
                uf.union(v,ver.get(0));
            }
        }

        return true;
    }

    class UnionFind{
        int[] parent;
        int count;

        UnionFind(int n){
            parent = new int[n+1];
            count = n;
            for(int i=1;i<=n;i++){
                parent[i] = i;
            }
        }

        int find(int x){
            if(x!=parent[x]){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x,int y){
            int newX = find(x);
            int newY = find(y);
            if(newX==newY){
                return;
            }
            parent[newY] = newX;
            count--;
        }

        boolean connect(int x,int y){
            int newX = find(x);
            int newY = find(y);
            return newX == newY;
        }
    }
}
